package arr

/*
差分数组
时间复杂度:O(N+k) k表示updates的长度
空间复杂度:O(N)
*/

func getModifiedArray(length int, updates [][]int) []int {
	// 差分数组的定义: diff[i] = nums[i]-nums[i-1]
	// 如果对某个区间nums[i:j]进行增加x
	// 则对差分数组diff[i:j]范围内的差值是不变的(均增加x), nums[i]比nums[i-1]的差值增加了x， nums[j+1]比nums[j]的差值减少了x
	diff := make([]int, length)
	for _, v := range updates {
		diff[v[0]] += v[2]
		if v[1]+1 < length {
			diff[v[1]+1] -= v[2]
		}
	}

	for i := 1; i < length; i++ {
		diff[i] += diff[i-1]
	}
	return diff
}
